%% /usr/local/src/lcc/lcc-4.1.beta.6/README.x86, Thu Mar 22 11:35:01 2001
%% Edit by Nelson H. F. Beebe <beebe@math.utah.edu>

FOREWORD: This file documents the experiments made over several hours
          on 22-Mar-2001 that ultimately led to a solution of the
          long-standing "make triple" compiler self-bootstrap test
          failure on Intel x86 platforms.

The triple test fails on Intel x86.  The two [12]rcc executables
differ wildly in sizes, when they should be identical.

Tests with an extended Makefile that saves .s files for both x86/linux
and sparc/solaris showed a curious feature: 25 of the 36 .s files
differ, and exactly the same ones differ for the two code generators!

These differ:

	alpha.s		  expr.s	    simp.s	      trace.s
	bytecode.s	  gen.s		    sparc.s	      tree.s
	dag.s		  init.s	    stab.s	      types.s
	dagcheck.s	  lex.s		    stmt.s	      x86.s
	decl.s		  mips.s	    sym.s	      x86linux.s
	enode.s		  output.s	    symbolic.s	      x86solaris.s
	error.s

These are the same:

	alloc.s		  inits.s	    main.s	      prof.s
	bind.s		  input.s	    null.s	      string.s
	event.s		  list.s	    profio.s

Of these 11 matches, 8 are the smallest .s files produced!

The differences seem to be in the label numbers.  In the error.s
files, there appear to be jump tables of different lengths, suggesting
that the -d0.6 option, which controls jump table density, might be the
culprit.

A test was then made with the default, -d0.5.  There are again
differences, this time in 23 files, and the same files differ for the
two target architectures.

A third test was made with -d0.  Now the .s files are identical!
YEAHHHH!  However, one of the compiler back ends failed to link

A fourth test was math with -d1.  The .s files are again identical!
However, one of the compiler back ends again failed to link.  For ALL
settings of the -d value, rcc complains:

	/usr/tmp/lcc/4.1.beta.6/x86/linux/alpha.c:4391: warning: switch generates a huge table
	/usr/tmp/lcc/4.1.beta.6/x86/linux/mips.c:3486: warning: switch generates a huge table
	/usr/tmp/lcc/4.1.beta.6/x86/linux/sparc.c:4379: warning: switch generates a huge table
	/usr/tmp/lcc/4.1.beta.6/x86/linux/x86.c:5045: warning: switch generates a huge table
	/usr/tmp/lcc/4.1.beta.6/x86/linux/x86linux.c:6224: warning: switch generates a huge table
	/usr/tmp/lcc/4.1.beta.6/x86/linux/x86solaris.c:6231: warning: switch generates a huge table

The lcc -d#.# switch gets passed to rcc as -s#.#.  rcc parses it in
src/main.c:166 in the line

	density = strtod(&argv[i][2], NULL);

That variable is used in the code like this:

	% egrep -n -e density *.[ch] *.md /dev/null
	c.h:683:extern float density;
	main.c:166:			density = strtod(&argv[i][2], NULL);
	stmt.c:11:float density = 0.5;
	stmt.c:400:		while (n > 0 && den(n-1, k) >= density)

------------------------------------------------------------------------
I found that lcc must be built from scratch each time the triple test
is run, so the above remarks on the -d# values are suspect.

I repeated them with "make clobber all check-3" runs, with different
choices of the # value:

	-d1.0		: 25 out of 36 .s files differ
	-d0.5		: 23 out of 36 .s files differ
	-d0.03125	: 12 out of 36 .s files differ
	-d0.0		: all .s files identical, and triple test passed!

The largest .s file from a normal .c file with -d0.0 is decl.s.  Here
is how the size changes as a function of the -d value:

foreach f ( \
		0 \
		0.00390625 \
		0.0078125 \
		0.015625 \
		0.03125 \
		0.0625 \
		0.125 \
		0.25 \
		0.5 \
		1 \
	)
	/bin/rm -f decl.s
	echo ======= -d$f
	lcc -S -d$f ../lcc-4.1.beta.6/src/decl.c
	ls -l decl.s
end

======= -d0		-rw-rw-r--    1 beebe    wheel      114379 Mar 22 07:25 decl.s
======= -d0.00390625	-rw-rw-r--    1 beebe    wheel      114379 Mar 22 07:25 decl.s
======= -d0.0078125	-rw-rw-r--    1 beebe    wheel      114379 Mar 22 07:25 decl.s
======= -d0.015625	-rw-rw-r--    1 beebe    wheel      114379 Mar 22 07:25 decl.s
======= -d0.03125	-rw-rw-r--    1 beebe    wheel      114379 Mar 22 07:25 decl.s
======= -d0.0625	-rw-rw-r--    1 beebe    wheel      114410 Mar 22 07:25 decl.s
======= -d0.125		-rw-rw-r--    1 beebe    wheel      113662 Mar 22 07:25 decl.s
======= -d0.25		-rw-rw-r--    1 beebe    wheel      113381 Mar 22 07:25 decl.s
======= -d0.5		-rw-rw-r--    1 beebe    wheel      113142 Mar 22 07:25 decl.s
======= -d1		-rw-rw-r--    1 beebe    wheel      113326 Mar 22 07:25 decl.s

Here is the same experiment for the largest C file:
/var/tmp/lcc/4.1.beta.6/x86/linux/x86solaris.c:

======= -d0		-rw-rw-r--    1 beebe    wheel      661876 Mar 22 07:28 x86solaris.s
======= -d0.00390625	-rw-rw-r--    1 beebe    wheel      661876 Mar 22 07:28 x86solaris.s
======= -d0.0078125	-rw-rw-r--    1 beebe    wheel      661876 Mar 22 07:28 x86solaris.s
======= -d0.015625	-rw-rw-r--    1 beebe    wheel      562703 Mar 22 07:28 x86solaris.s
======= -d0.03125	-rw-rw-r--    1 beebe    wheel      492720 Mar 22 07:28 x86solaris.s
======= -d0.0625	-rw-rw-r--    1 beebe    wheel      456613 Mar 22 07:28 x86solaris.s
======= -d0.125		-rw-rw-r--    1 beebe    wheel      448979 Mar 22 07:28 x86solaris.s
======= -d0.25		-rw-rw-r--    1 beebe    wheel      444395 Mar 22 07:28 x86solaris.s
======= -d0.5		-rw-rw-r--    1 beebe    wheel      443094 Mar 22 07:28 x86solaris.s
======= -d1		-rw-rw-r--    1 beebe    wheel      442935 Mar 22 07:28 x86solaris.s

That produced 

	/var/tmp/lcc/4.1.beta.6/x86/linux/x86solaris.c:6231: warning: switch generates a huge table

for -d0, -d0.00390625, and -d0.0078125.

------------------------------------------------------------------------

The next experiment is to see whether changing the type of the density
variable, and the den() macro from float to double will make the
results consistent.

diff $S/lcc/lcc-4.1.beta.6/src/c.h ../lcc-4.1.beta.6/src/c.h
683c683
< extern float density;
---
> extern double density;

diff $S/lcc/lcc-4.1.beta.6/src/stmt.c ../lcc-4.1.beta.6/src/
7c7
< #define den(i,j) ((j-buckets[i]+1.0)/(v[j]-v[buckets[i]]+1))
---
> #define den(i,j) ((double)(j-buckets[i]+1.0)/(double)(v[j]-v[buckets[i]]+1))
11c11
< float density = 0.5;
---
> double density = 0.5;

Here are the results:
	-d0.0		: all .s files identical, and triple test passed!
	-d0.03125	: 12 .s files differ
	-d0.5		: 23 .s files differ
	-d1.0		: 25 .s files differ

Thus, it appears that the only way to get the triple test to pass on
this platform is to use -d0 instead of the current -d0.6.

Here is a comparison of the component sizes:

-d1:
-rwxrwxr-x    1 beebe    wheel     1510353 Mar 22 07:57 /usr/tmp/lcc/4.1.beta.6/x86/linux/1rcc
-rwxrwxr-x    1 beebe    wheel     1961553 Mar 22 07:58 /usr/tmp/lcc/4.1.beta.6/x86/linux/2rcc
-rw-rw-r--    1 beebe    wheel     1953802 Mar 22 07:57 /usr/tmp/lcc/4.1.beta.6/x86/linux/librcc.a
-rwxrwxr-x    1 beebe    wheel     1138808 Mar 22 07:57 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc
-rw-rw-r--    1 beebe    wheel     1509841 Mar 22 07:58 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc1
-rw-rw-r--    1 beebe    wheel     1961041 Mar 22 07:58 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc2

-d0.5:
-rwxrwxr-x    1 beebe    wheel     1508113 Mar 22 07:50 /usr/tmp/lcc/4.1.beta.6/x86/linux/1rcc
-rwxrwxr-x    1 beebe    wheel     1961553 Mar 22 07:50 /usr/tmp/lcc/4.1.beta.6/x86/linux/2rcc
-rw-rw-r--    1 beebe    wheel     1953802 Mar 22 07:50 /usr/tmp/lcc/4.1.beta.6/x86/linux/librcc.a
-rwxrwxr-x    1 beebe    wheel     1138808 Mar 22 07:50 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc
-rw-rw-r--    1 beebe    wheel     1507601 Mar 22 07:50 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc1
-rw-rw-r--    1 beebe    wheel     1961041 Mar 22 07:50 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc2

-d0.03125:
-rwxrwxr-x    1 beebe    wheel     1608561 Mar 22 07:46 /usr/tmp/lcc/4.1.beta.6/x86/linux/1rcc
-rwxrwxr-x    1 beebe    wheel     1961553 Mar 22 07:46 /usr/tmp/lcc/4.1.beta.6/x86/linux/2rcc
-rw-rw-r--    1 beebe    wheel     1953802 Mar 22 07:45 /usr/tmp/lcc/4.1.beta.6/x86/linux/librcc.a
-rwxrwxr-x    1 beebe    wheel     1138808 Mar 22 07:45 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc
-rw-rw-r--    1 beebe    wheel     1608049 Mar 22 07:46 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc1
-rw-rw-r--    1 beebe    wheel     1961041 Mar 22 07:46 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc2

-d0.0:
-rwxrwxr-x    1 beebe    wheel     1961553 Mar 22 07:15 /usr/tmp/lcc/4.1.beta.6/x86/linux/1rcc
-rwxrwxr-x    1 beebe    wheel     1961553 Mar 22 07:15 /usr/tmp/lcc/4.1.beta.6/x86/linux/2rcc
-rw-rw-r--    1 beebe    wheel     1953802 Mar 22 07:15 /usr/tmp/lcc/4.1.beta.6/x86/linux/librcc.a
-rwxrwxr-x    1 beebe    wheel     1961553 Mar 22 07:15 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc
-rw-rw-r--    1 beebe    wheel     1961041 Mar 22 07:16 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc1
-rw-rw-r--    1 beebe    wheel     1961041 Mar 22 07:16 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc2


In the triple test, rcc1 and rcc2 are compared (ignoring their first
512 bytes), and if they match, 2rcc replaces rcc.  2rcc was produced
by compiling lcc with itself, whereas 1rcc was produced by compiling
lcc using the rcc component built with the native compiler.

The 2rcc files have identical sizes:

-d1:
-rwxrwxr-x    1 beebe    wheel     1961553 Mar 22 07:58 /usr/tmp/lcc/4.1.beta.6/x86/linux/2rcc

-d0.5:
-rwxrwxr-x    1 beebe    wheel     1961553 Mar 22 07:50 /usr/tmp/lcc/4.1.beta.6/x86/linux/2rcc

-d0.03125:
-rwxrwxr-x    1 beebe    wheel     1961553 Mar 22 07:46 /usr/tmp/lcc/4.1.beta.6/x86/linux/2rcc

-d0.0:
-rwxrwxr-x    1 beebe    wheel     1961553 Mar 22 07:15 /usr/tmp/lcc/4.1.beta.6/x86/linux/2rcc

The tradeoff is that the native compiler produced an rcc file of this
size:

-rwxrwxr-x    1 beebe    wheel     1138808 Mar 22 07:57 /usr/tmp/lcc/4.1.beta.6/x86/linux/rcc

Thus, using d0 to get consistent jump tables produces a blowup of
1961553 / 1138808 = 1.72 in the size of the rcc component.

------------------------------------------------------------------------
The next experiment is based on the suspicion that the failures of the
triple tests might be due to different handling of floating-point
expressions.  If one compiler stores values in memory, while the other
keeps them in registers, then on any platform where the registers have
longer sizes (e.g., MC68K, Intel x86, Intel IA-64, ...), we should
expect differences, but on systems where they have the same size, we
should get the same answer.  The fact that the triple test succeeds on
Compaq/DEC, SGI, and Sun systems, which have identical register and
memory word sizes, is highly suggestive!

I therefore patched src/stmt.c, and made runs with these source code
differences:

========================================================================
Temporary source code patches:

diff -r /usr/local/src/lcc/lcc-4.1.beta.6/src/c.h ../lcc-4.1.beta.6/src/c.h
683c683
< extern float density;
---
> extern double density;

diff -r /usr/local/src/lcc/lcc-4.1.beta.6/src/stmt.c ../lcc-4.1.beta.6/src/stmt.c
7c7,8
< #define den(i,j) ((j-buckets[i]+1.0)/(v[j]-v[buckets[i]]+1))
---
> #define den(i,j) dstore(dstore((double)(j-buckets[i]+1))/dstore((double)(v[j]-v[buckets[i]]+1)))
> static double dstore(double x);
11c12
< float density = 0.5;
---
> double density = 0.5;
705a707,710
> }
>
> static double dstore(double x) {
>     return (x);
========================================================================

	-d1.000		: triple PASSED!
	-d0.6		: triple PASSED!
	-d0.03125	: triple PASSED!
	-d0.0000	: triple PASSED!

**********
**********
** QED! **
**********
**********

------------------------------------------------------------------------
P.S. I also tried defining density with its original float type, and
using (float)dstore(...) in the den() macro.  That produced
differences in lex.s, sparc.s, and trace.s, and another triple test
failure.  Thus, density MUST be promoted to double.

---------------------------[The End, At Last]---------------------------
